package 双指针;


/**
 * @description:
 * @author: ywk
 * @date: 2021-01-08
 */
public class 计算面积 {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 0, 1, 0, 0, 1};
        calMaxArea(arr);
        calMaxAreaMemo(arr);
    }

    private static void  calMaxArea(int[] arr) {
        int leftMax = arr[0], rightMax = arr[arr.length - 1];
        int left = 0, right = arr.length - 1;
        int sum = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, arr[left]);
            rightMax = Math.max(rightMax, arr[right]);
            if (leftMax < rightMax) {
                sum += leftMax - arr[left];
                left++;
            }else{
                sum += rightMax - arr[right];
                right--;
            }
        }
        System.out.println(sum);
    }
    private static void  calMaxAreaMemo(int[] arr) {
        int leftMax = 0;
        int sum = 0;
        int[] maxLeftArr = new int[arr.length];
        int[] maxRightArr = new int[arr.length];
        int left = arr[0], right = arr[arr.length - 1];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < left) {
                maxLeftArr[i] = left;
            }else{
                left = arr[i];
            }
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] < right) {
                maxRightArr[i] = right;
            } else {
                right = arr[i];
            }
        }
        for (int i = 1; i < arr.length-1; i++) {
            int val = Math.min(maxLeftArr[i], maxRightArr[i]) - arr[i];
            sum += val > 0 ? val : 0;


        }
        System.out.println(sum);
    }
}
